package com.taijia.chapter2;

/**
 * fabonacci数列  递归解决
 * 
 * @author taijia
 * @since 2014年9月27日
 *
 */
public class Fab {
	
	public static void main(String[] args) {
		System.out.println(fab(40));
		System.out.println(fabfor(40));
	}

	/**
	 * 用递归实现
	 * @param n
	 * @return
	 */
	public static long fab(long n) {
		if (n <= 2) {
			return 1;
		} else {
			return fab(n - 1) + fab(n - 2);
		}
	}
	
	/**
	 * 用循环实现
	 * @param n
	 * @return
	 */
	public static long fabfor(long n) {
		long result = 0;
		long fn1 = 1;
		long fn2 = 1;
		for(long i = 1;i<=n;i++) {
			if(i==1 || i==2) {
				result = 1;
			} else {
				result=fn1+fn2;
				fn2 = fn1;
				fn1 = result;
			}
		}
		return result;
	}
}
